package cn.dlc.com.sort;

import java.util.Arrays;

/**
 * @author 邓立川
 * @date 2021/3/14 9:14
 * @desc 插入排序
 */
public class Demo10 {

    public static void main(String[] args) {
        Integer[] arr = {4,3,2,10,12,1,5,6};
        InsertSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void InsertSort(Comparable[] arr){

        // 确定被比较的元素，没有排序的(一开始获取的就是第二个)
        for(int i = 1 ; i < arr.length; i++) {
            // 拿比较的元素依次和它前面的元素比较，
            // 如果前面的元素更大就交换位置，
            for(int j = i ; j >= 1; j-- ) {
                // 和它前面的元素比较，所以注意索引
                if(SortUtils.greater(arr[j-1],arr[j])) {
                    // 排序好的比没有排序的大，交换
                    SortUtils.exchange(arr,j-1,j);
                } else {
                    // 没有找到，比如上面的10,12
                    break;
                }
            }
        }
    }
}
